package com.itheima.leetcode.od.b.graph.topo;

import com.itheima.datastructure.graph.Edge;
import com.itheima.datastructure.graph.Vertex;

import java.util.*;
import java.util.stream.Collectors;

/**
 * (C卷,200分)- 启动多任务排序（Java & JS & Python & C）
 * <p>
 * 题目描述
 * <p>
 * 一个应用启动时，会有多个初始化任务需要执行，并且任务之间有依赖关系，例如A任务依赖B任务，那么必须在B任务执行完成之后，才能开始执行A任务。
 * <p>
 * 现在给出多条任务依赖关系的规则，请输入任务的顺序执行序列，规则采用贪婪策略，即一个任务如果没有依赖的任务，则立刻开始执行，如果同时有多个任务要执行，则根据任务名称字母顺序排序。
 * <p>
 * 例如：B任务依赖A任务，C任务依赖A任务，D任务依赖B任务和C任务，同时，D任务还依赖E任务。那么执行任务的顺序由先到后是：
 * <p>
 * A任务，E任务，B任务，C任务，D任务
 * <p>
 * 这里A和E任务都是没有依赖的，立即执行。
 * <p>
 * 输入描述
 * <p>
 * 输入参数每个元素都表示任意两个任务之间的依赖关系，输入参数中符号"->"表示依赖方向，例如：
 * <p>
 * A->B：表示A依赖B
 * <p>
 * 多个依赖之间用单个空格分隔
 * <p>
 * 输出描述
 * <p>
 * 输出排序后的启动任务列表，多个任务之间用单个空格分隔
 * <p>
 * 用例
 * 输入	A->B C->B
 * 输出	B A C
 * 说明	无
 * <p>
 * 题目解析
 * <p>
 * 本题是拓扑排序问题，本题解析可以参考下面博客：
 * <p>
 * LeetCode - 207 课程表_leetcode207课程表-CSDN博客
 * <p>
 * 本题没有说明循环依赖的情况该如何处理，因此我认为本题没有循环依赖的情况。实际考试需要注意下。
 */
public class StartMultitaskingSorting {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        String[][] relations =
                Arrays.stream(sc.nextLine().split(" ")).map(s -> s.split("->")).toArray(String[][]::new);*/

//        String relationsStr = "A->B C->B";
//        String relationsStr = "B->A C->A D->B D->C D->E"; // 这个条件输入很特殊，自带排序
        String relationsStr = "E->A B->A C->A D->B D->C";
        System.out.println(getResult(relationsStr));
        System.out.println(getResult2(relationsStr)); // 建议使用通用的顶点类（Vertex）+ 边类（Edge），自定义拓扑相关类的解题代码可读性极差
    }

    /**
     * 用的是拓扑的概念，next就相当于 顶点类（Vertex）+ 边类（Edge），inDegree就是顶点的入度，换汤不换药
     *
     * @param relationsStr
     * @return
     */
    public static String getResult(String relationsStr) {
        String[][] relations =
                Arrays.stream(relationsStr.split(" ")).map(s -> s.split("->")).toArray(String[][]::new);
        HashMap<String, Integer> inDegree = new HashMap<>();
        HashMap<String, ArrayList<String>> next = new HashMap<>();

        for (String[] relation : relations) {
            // a依赖b, 即b执行完，才能执行a
            String a = relation[0];
            String b = relation[1];

            // b的入度不变
            inDegree.put(b, inDegree.getOrDefault(b, 0));
            // a的入度+1
            inDegree.put(a, inDegree.getOrDefault(a, 0) + 1);

            // b的后继节点集合添加a
            next.putIfAbsent(b, new ArrayList<>());
            next.get(b).add(a);
            // a的后继节点集合不变
            next.putIfAbsent(a, new ArrayList<>());
        }

        // queue收集第一层入度为0的点
        ArrayList<String> queue = new ArrayList<>();
        for (String task : inDegree.keySet()) {
            if (inDegree.get(task) == 0) {
                queue.add(task);
            }
        }

        // 记录任务执行的顺序
        StringJoiner ans = new StringJoiner(" ");

        while (queue.size() > 0) {
            // 如果同时有多个任务要执行，则根据任务名称字母顺序排序
            queue.sort(String::compareTo);

            // result用于记录下一层入度为0的点
            ArrayList<String> result = new ArrayList<>();

            for (String fa : queue) {
                // fa执行，则加入已完成的任务列表
                ans.add(fa);

                for (String ch : next.get(fa)) {
                    // fa是父任务，ch是子任务, 即fa执行完，才能执行ch
                    // fa执行完，则对应ch的入度-1
                    inDegree.put(ch, inDegree.get(ch) - 1);

                    // 如果ch的入度变为0，则加入新一层入度0的点集
                    if (inDegree.get(ch) == 0) {
                        result.add(ch);
                    }
                }
            }

            queue = result;
        }

        return ans.toString();
    }

    /**
     * 拓扑的广度遍历，有点炫技了，我写滴比作者可读性更差
     *
     * @param relationsStr
     * @return
     */
    public static String getResult2(String relationsStr) {

        /**
         * 将所有的参数初始化进 图（用map装）
         */
        HashMap<String, Vertex> graph = new HashMap<>();
        Arrays.stream(relationsStr.split(" "))
                .map(s -> s.split("->"))
                .forEach(strings -> {
                            graph.putIfAbsent(strings[0], new Vertex(strings[0]));
                            graph.putIfAbsent(strings[1], new Vertex(strings[1]));
                            graph.get(strings[1]).edges.add(new Edge(graph.get(strings[0])));
                        }
                );

        Collection<Vertex> vertices = graph.values();
        for (Vertex vertex : vertices) {
            for (Edge edge : vertex.edges) {
                edge.linked.inDegree++;
            }
        }

        LinkedList<Vertex> curQueue = new LinkedList<>();
        List<String> result = new ArrayList<>();
        for (Vertex vertex : vertices) {
            if (0 == vertex.inDegree) {
                curQueue.offer(vertex);
            }
        }

        // 敲重点，这里需要通过定义一个临时的 nextQueue 来进行广度按层排序
        while (!curQueue.isEmpty()) {
            LinkedList<Vertex> nextQueue = new LinkedList<>();
            while (!curQueue.isEmpty()) {
                Vertex vertex = curQueue.poll();
                result.add(vertex.name);
                for (Edge edge : vertex.edges) {
                    if (0 == --edge.linked.inDegree) {
                        nextQueue.offer(edge.linked);
                    }
                }
            }
            curQueue = nextQueue;
            curQueue.sort((a, b) -> a.name.compareTo(b.name)); // 升序排序（小顶堆）
        }

        if (graph.size() != result.size()) { // 图的题目天生要判断环
            return "存在环";
        } else {
            return result.stream().collect(Collectors.joining(" "));
        }
    }
}

